package william.quicksort;

/**
 * @author ZhangShenao
 * @date 2024/1/29
 * @description <a href="https://leetcode.cn/problems/sort-colors/description/">...</a>
 */
public class Leetcode75_颜色分类_快速排序 {
    /**
     * 采用快速排序思想
     * 本质上就是以1为基准值，将整个数组划分成3个区域：小于1区、等于1区和大于1区。
     * 维护两个区域：小于区 [0,less] 和 大于区 [more,arr.length-1]。在小于区内，所有元素均 < 1；在大于区内，所有元素均 >1。
     * 初始化时，less = -1，more = arr.length。
     * 遍历数组，针对每一个元素，可能存在三种情况：
     * - 该元素 == 1，无需任何处理，直接跳到下一个元素。
     * - 该元素 < 1，则将该元素与小于区的下一个元素进行交换，同时将小于区向右移动一位，并跳到下一个元素。
     * - 该元素 > 1，则将该元素与大于区的前一个元素进行交换，同时将大于区向左移动一位。此时不跳下一个元素，因为该元素是刚交换过来的，还没有处理过。
     * 重复上述过程，直到当前元素与大于区的第一个元素相遇。
     * 实际上，上述过程就是小于区 [0,less] 和 大于区 [more,arr.length-1]两个区域，同时从两侧将等于区往中间推。
     */
    public void sortColors(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return;
        }

        //维护两个区域 小于区[0,less] 大于区[more,N-1]
        int N = nums.length;
        int less = -1;
        int more = N;


        //遍历数组,判断每个元素的大小
        int i = 0;
        while (i < more) {   //终止条件:到达大于区
            int n = nums[i];
            if (n == 1) { //元素==1,无需处理,继续判断下一个元素
                i++;
            } else if (n < 1) {   //元素<1,将该元素与less的下一个元素交换,并将less后移一位,继续判断下一个元素
                swap(nums, ++less, i++);
            } else {    //元素>1,将该元素与more的前一个元素交换,并将more前移一位,继续判断新交换过来的元素
                swap(nums, --more, i);
            }
        }
    }

    /**
     * 将数组nums中i和j两个下标处的元素进行交换
     */
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
